﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TextEditApp.Algorithm
{
    class Trie
    {
        bool isEnd;
        Trie[] childTries = new Trie[26];

        /// <summary>
        /// 向字典树插入单词
        /// </summary>
        /// <param name="word"></param>
        public void Insert(string word)
        {
            Trie current = this;
            foreach (var c in word)
            {
                if (current.childTries[c - 'a'] == null) current.childTries[c - 'a'] = new Trie();
                current = current.childTries[c - 'a'];
            }

            current.isEnd = true;
        }

        /// <summary>
        /// 查询单词是否在树中
        /// </summary>
        /// <param name="word"></param>
        /// <returns></returns>
        public bool Search(string word)
        {
            Trie current = this;
            foreach (var c in word)
            {
                if (c < 'a' || c > 'z') return false;
                if (current.childTries[c - 'a'] == null) return false;
                current = current.childTries[c - 'a'];
            }

            return current.isEnd;
        }

        /// <summary>
        /// 查询前缀
        /// </summary>
        /// <param name="prefix"></param>
        /// <returns></returns>
        public bool StartsWith(string prefix)
        {
            Trie current = this;
            foreach (var c in prefix)
            {
                if (c < 'a' || c > 'z') return false;
                if (current.childTries[c - 'a'] == null) return false;
                current = current.childTries[c - 'a'];
            }

            return true;
        }
    }
}
